#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 字符串匹配
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length();
        int m = p.length();
        bool f[n + 1][m + 1];
        memset(f, 0, sizeof(f));

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // 分成空正则和非空正则两种
                if (j == 0) {
                    // 空正则
                    f[i][j] = (i == 0);
                }
                else {
                    // 非空正则分为两种情况 * 和 非*
                    if (p[j - 1] != '*') {
                        if (i > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))
                            f[i][j] = f[i - 1][j - 1];
                    }
                    else {
                        // 碰到 * 了，分为看和不看两种情况
                        // 不看
                        if (j >= 2) {
                            f[i][j] |= f[i][j - 2];
                        }
                        // 看
                        if (i >= 1 && j >= 2 && (s[i - 1] == p[j - 2] || p[j - 2] == '.')) {
                            f[i][j] |= f[i - 1][j];
                        }
                    }
                }
            }
        }
        return f[n][m];
    }
};